package com.markus.code.动态规划;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * Author:markusZhang
 * Date:Create in 2020/8/15 12:44
 * todo: 最长公共子序列问题
 */
public class LCSDemo {
    /**
     * 第一个场景：要求去最长公共子序列的长度
     * 这是一个 用一个样本做行，一个样本做列的尝试模型
     * 定义：dp[i][j]的情况有四种
     *      1、当最长公共子序列既不以str1[i]结尾，也不以str2[j]结尾的情况
     *          dp[i][j] = dp[i-1][j-1]
     *      2、当最长公共子序列不以str1[i]结尾，以str2[j]结尾的情况
     *          dp[i][j] = dp[i-1][j]
     *      3、当最长公共子序列以str1[i]结尾，不以str2[j]结尾的情况
     *          dp[i][j] = dp[i][j-1]
     *      4、当最长公共子序列以str1[i]结尾，以str2[j]结尾的情况
     *          dp[i][j] = dp[i-1][j-1]+1
     */
    public int lcsLength(String s1,String s2){
        if (s1 == null || s1.length() == 0 || s2 == null || s1.length() == 0){
            return 0;
        }
        char[] str1 = s1.toCharArray();
        //原字符串的倒置
        char[] str2 = s2.toCharArray();
        //声明dp数组，dp[i][j]为两个字符串比较到str1[i],str2[j]的相同子序列的最大长度
        int dp[][] = new int[str1.length][str2.length];
        dp[0][0] = str1[0] == str2[0] ? 1 : 0;
        for (int i = 1; i < str2.length; i++) {
            dp[0][i] = str2[i] == str1[0] ? 1 : dp[0][i-1];
        }
        for (int i = 1; i < str1.length; i++) {
            dp[i][0] = str2[0] == str1[i] ? 1 : dp[i-1][0];
        }
        for (int i = 1; i < str1.length; i++) {
            for (int j = 1; j < str2.length; j++) {
                dp[i][j] = Math.max(Math.max(dp[i - 1][j - 1], dp[i][j - 1]),dp[i-1][j]);
                if (str1[i] == str2[j]){
                    dp[i][j] = Math.max(dp[i-1][j-1]+1,dp[i][j]);
                }
            }
        }
        return dp[str1.length-1][str2.length-1];
    }

    /**
     * 接下来就是对上题做一个空间压缩
     * 这个题是依赖左上、上、左的一个模型
     */
    public int lcsLengthPushSpace(String s1,String s2){
        if (s1 == null || s1.length() == 0 || s2 == null || s1.length() == 0){
            return 0;
        }
        char []str1 = s1.toCharArray();
        char []str2 = s2.toCharArray();
        int dp[] = new int[str2.length];
        dp[0] = str1[0]==str2[0] ? 1:0;
        for (int i = 1; i < dp.length ; i++){
            dp[i] = str1[0] == str2[i] ? 1 : dp[i-1];
        }
        for (int i=1;i<str1.length;i++){
            int temp = dp[0];
            dp[0] = str1[i] == str2[0] ? 1 : dp[0];
            for (int j=1;j<dp.length;j++){
                int leftUp = temp;
                temp = dp[j];
                dp[j] = Math.max(dp[j],dp[j-1]);
                if (str1[i] == str2[j]){
                    dp[j] = Math.max(dp[j],leftUp+1);
                }
            }
        }
        return dp[str2.length-1];
    }

    /**
     * 接下来就是这个题的变种：我想要得到这个最长公共子序列是什么？
     * 建立一张二维表，然后回溯。这张二维表示不能进行空间压缩的，如果被压缩了，就不能进行回溯了
     */
    public String lcs(String str1,String str2){
        if (str1 == null || str1.length() == 0 || str2 == null || str1.length() == 0){
            return "";
        }
        int[][] dp = getDp(str1, str2);
        StringBuilder sb = new StringBuilder();
        //通过这张二维表进行回溯,从最后一个元素出发
        for (int i=str1.length()-1;i>=0;){
            for (int j=str2.length()-1;j>=0;){
                //先判断i、j对应的两个字符是否相等
                //如果相等，看看左上的值+1与左、上的大小
                if (str1.charAt(i) == str2.charAt(j)){
                    if (dp[i-1][j-1]+1 == dp[i][j]){
                        sb.append(str1.charAt(i));
                        j--;
                        i--;
                        continue;
                    }
                }
                if (i!=0 && j!=0){
                    if (dp[i-1][j]>dp[i][j-1]){
                        i--;
                    }else{
                        j--;
                    }
                }else if (i!=0){
                    i--;
                }else if (j!=0){
                    j--;
                }else{
                    i--;
                    j--;
                }
            }
        }
        return sb.reverse().toString();
    }
    private int[][] getDp(String s1,String s2){
        if (s1 == null || s1.length() == 0 || s2 == null || s1.length() == 0){
            return new int[0][0];
        }
        char[] str1 = s1.toCharArray();
        //原字符串的倒置
        char[] str2 = s2.toCharArray();
        //声明dp数组，dp[i][j]为两个字符串比较到str1[i],str2[j]的相同子序列的最大长度
        int dp[][] = new int[str1.length][str2.length];
        dp[0][0] = str1[0] == str2[0] ? 1 : 0;
        for (int i = 1; i < str2.length; i++) {
            dp[0][i] = str2[i] == str1[0] ? 1 : dp[0][i-1];
        }
        for (int i = 1; i < str1.length; i++) {
            dp[i][0] = str2[0] == str1[i] ? 1 : dp[i-1][0];
        }
        for (int i = 1; i < str1.length; i++) {
            for (int j = 1; j < str2.length; j++) {
                dp[i][j] = Math.max(Math.max(dp[i - 1][j - 1], dp[i][j - 1]),dp[i-1][j]);
                if (str1[i] == str2[j]){
                    dp[i][j] = Math.max(dp[i-1][j-1]+1,dp[i][j]);
                }
            }
        }
        return dp;
    }

    /**
     * 求出所有的最长公共子序列问题
     */
//    public List<String> allLcs(String str1,String str2){
//        List<String> res = new ArrayList<>();
//        if (str1 == null || str1.length() == 0 || str2 == null || str2.length() == 0){
//            return res;
//        }
//        int[][] dp = getDp(str1, str2);
//
//    }
//    private void process(int [][]dp,char[] str1,char[] str2,int row,int col,StringBuilder path,List<String> res){
//        if (row == 0 && col == 0){
//            if (!res.contains(path)){
//                res.add(path.toString());
//            }
//            return ;
//        }
//        if (row < 0 || col < 0){
//            return ;
//        }
//        if (str1[row] == str2[col]){
//            if (dp[row-1][col]){
//
//            }
//
//        }
//
//    }
    @Test
    public void test(){
        String s1 = "a1b2bca3d" ;
        String s2 = "56abb8a89" ;

        int row = s1.length() ;
        int lin = s2.length() ;

        char[] chars1 = s1.toCharArray() ;
        char[] chars2 = s2.toCharArray() ;

        int[][] dp = new int[row][lin] ;
        for (int i=0 ; i<row ; i++){
            for (int j=0 ; j<lin ; j++){
                dp[i][j] = chars1[i] == chars2[j] ? 1 : 0 ;
            }
        }
        int index = 0 ;
        StringBuilder sb = new StringBuilder();
        for (int i=0 ; i<row ; i++){
            for (int j=index ; j<lin ; j++){
                if (dp[i][j] == 1){
                    sb.append(chars1[i]) ;
                    index = j+1 ;
                    break ;
                }
            }
        }
        System.out.println(sb.toString());
    }

    public static void main(String[] args) {
        String str1 = "ezupkr";
        String str2 = "ubmrapg";
        LCSDemo demo = new LCSDemo();
        System.out.println(demo.lcsLength(str1,str2));
//        System.out.println(demo.lcsLengthPushSpace(str1,str2));
//        System.out.println(demo.lcs(str1,str2));
    }
}
